package 快排;

import java.util.Random;


//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//
//请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//
//你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
public class Solution2 {
    public int findKthLargest(int[] nums, int k) {

        return qsort(nums, 0, nums.length - 1, k);
    }

    private int qsort(int[] nums, int l, int r, int k) {
        if(l==r){
            return nums[l];
        }
        int left=l-1,rigth=r+1,i=l;
        int key=nums[new Random().nextInt(r-l+1)+l];
        while(i<rigth){
            if(nums[i]<key){
                swap(nums,++left,i++);
            }else  if(nums[i]==key){
                i++;
            }else{
                swap(nums,--rigth,i);
            }
        }
        int c=r-rigth+1;
        int b=rigth-left-1;
        if(c<k){
            return qsort(nums,rigth,r,k);
        }else if(c+b>=k){
            return key;
        }else {
            return qsort(nums,l,left,k-b-c);
        }
    }

    private void swap(int[] nums, int i, int i1) {
        int tmp=nums[i];
        nums[i]=nums[i1];
        nums[i1]=tmp;
    }
}
